Many image processing applications, e.g., medical imaging, scientific visualization, multi-media presentations, etc., require high resolution, real color images to be manipulated and displayed. Professional workstation displays have image resolutions that range from 1K (lines) by 1K (pixels) to 2K by 2K. Pixel colors are represented by three bytes, one byte for each of the red, green and blue color components. In such systems, images are stored in a frame buffer having a capacity of three megabytes (MB) to 12 MB.
A frame buffer should have a video bandwidth approximately equal to the frame resolution (number of pixels), multiplied by the number of frames per second provided to the display system. Usually, the number of frames per second ranges from 30, for interlaced television monitors, to 60 or higher for non-interlaced displays. Thus, a frame buffer with a 1K by 1K resolution should provide 60 million pixels to a non-interlaced monitor input. The video clock (VCLK) which shifts data to the digital-to-analog converter from the memory should be higher than 60 Mhz. In reality, about 20% of a frame time is spent for horizontal and vertical fly-back and usually 80 Mhz is an appropriate VCLK frequency.
Using video random access memory (VRAM) chips with serial output port shift frequencies of 30 Mhz, three VRAM chips must work in parallel to provide a necessary video output bandwidth. (Usually, four VRAMs are used as they enable an easier implementation of the frame buffer input/output datapath.) Thus, the higher the resolution, the wider the bandwidth of the memory video path that is required and the greater the number of chips that must be activated in parallel. Furthermore, for high resolution the number of memory chips may, as a result of being operated in parallel, provide a greater amount of memory than that which is required for image storage and result in wasted memory space. Full motion images require double the memory for storage in order to eliminate the image tearing artifact. The so-called dual buffer approach allows one frame of storage to be updated while showing a previous frame. When a new frame is fully stored, half of the buffer storing the new frame is switched to digital-to-analog converters at the video output during the next vertical synch signal. Then, an update of the second half of the buffer starts with a next frame of data.
The requirements of spatial and color resolution, video bandwidth and double buffering may be satisfied only when using large frame buffers with a large number of expensive memory chips. One way to reduce the amount of memory is to compress an image according to standard compression methods. This enables the image to be stored in a smaller frame buffer and to be decompressed while reading the image from the frame buffer to the video channel. Major problems are presented by such storage techniques. First, contemporary approaches to image compression do not sufficiently preserve high frequency components that accompany graphic data or text. Second, commonly used comparison algorithms are too complex to enable decompression chips using such algorithms to exhibit a necessary high resolution video output bandwidth. Third, a majority of those algorithms require non-uniform image update access and leads to further decreases of video output bandwidth. Thus, while the amount of memory is reduced through the use of such compression/decompression techniques, it is difficult to apply such video buffers to high performance displays.
In FIG. 1, a conventional frame buffer architecture is illustrated and is shown providing a 1K by 1K resolution with 24 color bits per pixel. It includes four memory blocks, M0, M1, M2 and M3, a serializer 10, an oscillator 12, counter 14 and decoder 16. Each memory block M0-M3 includes several VRAM chips and has an internal address structure of 512 rows by 512 columns. Each individual row/column position holds twenty-four bits. Memory modules M0-M3 provide four (24 bit) adjacent pixels, in parallel, to serializer 10. Oscillator 12 generates a VCLK signal which serves as a clock frequency for four 24 bit registers, R0, R1, R2, and R3 within serializer 10. Clock signal VCLK is divided by a counter 14 to provide a serial clock signal (SCLK) with a frequency that is four times lower than VCLK. The SCLK signal shifts out the data from memory modules M0-M3. In specific, SCLK shifts data out of the VRAMS within modules M0-M3 from their secondary serial ports.
A decoder 16 generates a short pulse LD at each falling edge of SCLK (each pulse LD has a length of one VCLK). Pulse LD loads 96 bits from the VRAM secondary (serial) ports into the bit positions within serializer 10. The LD signal also controls a plurality of multiplexers M1-M3. In the absence of an active LD signal, the multiplexers are switched to a state to enable one register stage to pass its signal to a next stage. Thus, during a subsequent 3 VCLK periods, multiplexers M1-M3 connect registers R0-R3 into a shift register. As a result, four pixels are loaded into the serializer in parallel and shifted out sequentially as 24 bit color data to red, green, and blue digital-to-analog converters (not shown).
As can be seen from an examination of the buffer system shown in FIG. 1, in order to configure a 2K by 2K dual buffer without compression would require the use of 64-four megabyte chips. As will be seen hereinafter, compression/decompression enables substantial reduction in the amount of memory required for a 2K by 2K dual buffer (e.g., by a factor of 8).
A favored compression algorithm is a block truncation method that is described in detail by Healy et al., in "Digital Video Bandwidth Compression Using Truncation Coding", IEEE Transactions COMM, COM-9, Dec. 1981, pages 1809-1823. That compression algorithm provides high quality text and graphic image decompression and reasonable quality, television-like natural images. The compression method, per se, is not directly relevant to this invention and only certain aspects of it will be reviewed.
The basic idea of the algorithm is to represent each 4 by 4 region of pixels (48 bytes, assuming three bytes per pixel) with two colors, (three bytes each) plus a 16 bit wide MASK. The two colors are calculated statistically to best represent the distribution of colors in the 4 by 4 pixel region. The two colors are called Hi color and Lo color. Each MASK bit determines whether the corresponding pixel should get either a Hi or Lo color When the MASK bit value is a "1" then the corresponding pixel gets the Hi color; and when the MASK bit value is a "0" then the corresponding pixel gets the Lo color. This is illustrated in FIG. 2 which shows the bit mapping of a 4 by 4 pixel region 20 to its MASK 22.
The decompression mechanism is simpler than that of compression. For each 4 by 4 pixel matrix, a destination device receives two colors (Hi and Lo) and the 16 bit MASK. For each bit of the MASK, the corresponding pixel in the 4 by 4 pixel matrix gets either the Hi color, if the MASK bit is a 1 or the Lo color, if the MASK bit is a 0. FIG. 3 shows the compressed data format of an arbitrary 4 by 4 pixel area 24 where each pixel is either one of the colors, A or B.
The above-noted compression scheme has been employed in the prior art. In Campbell et al. U.S. Pat. No. 4,580,134, a color video display is described wherein a buffer memory uses two colors per pixel data matrix in the decoding action. Here, however, the bit MASK is employed to access color addresses which, in turn, access video look-up tables to find the actual color codes. For high performance systems, such video look-up tables do not provide adequate speed characteristics to enable the video bandwidth to be achieved at a reasonable cost.
In Tsai U.S. Pat. No. 4,797,729 a truncation coding system is described which evidences a tolerance to channel errors. Decompression occurs on the input to the buffer and full color pixel matrices are stored. A similar decompression arrangement is shown in Yamamuro et al. U.S. Pat. No. 4,908,610.
Other compression systems may be found in Music et al. U.S. Pat. No. 4,816,901 (employs differences in luminance functions between pixels to enable more compact encoding of run lengths of pixel data); Fedak et al. U.S. Pat. No. 4,555,802 (encodes image data by ignoring background data and transmits non-zero segments before background data, with offset and length numbers); and Chan et al. U.S. Pat. No. 4,729,127 (describes a mapping technique wherein delta code values enable access to stored, compacted map data).
Accordingly, it is an object of this invention to provide an improved image frame buffer that stores compressed image data for a high resolution, full color raster display.
It is another object of this invention to provide an improved compressed image frame buffer which exhibits a high efficiency in the decompression of the compressed image code.
It is still another object of this invention to provide an improved compressed image frame buffer which is able to provide video output consistent with the requirements of a high resolution full color raster display.